#include<stdio.h>
#include<windows.h>
#include<malloc.h>
//建立节点
typedef struct Node{
    int data;//数据域
    struct Node*next;//指针域
}linkStack;
//建立空栈
//链表不带头结点，初始化链栈只需要把栈顶置为空
void initStack(linkStack *&S){  //*&为引用，可以直接修改实参指向的位置
    S = (linkStack *)malloc(sizeof(linkStack));
    S -> next = NULL;   //栈为空
}
//判断空栈
int Empty(linkStack *S){    
    return (S -> next == NULL);
}
//销毁栈
void destoryStack(linkStack *&S){
    Node *p = S;
    while(S != NULL){
        S = S -> next;
        free(p);
        p = S;
    }
}
//入栈
void push(linkStack* &S,int x){
    linkStack *p;
    p = (linkStack*)malloc(sizeof(linkStack));      //创造一个工作节点
    p -> data = x;      //存入入栈信息
    p -> next = S -> next;
    S -> next = p;
}
//出栈
int pop(linkStack *&S,int &ptr){        //通过*ptr返回出栈的值
    linkStack *p = S -> next;
    if(S -> next == NULL){
        printf("空\n");
        return 0;
    }
    else{
        ptr = p -> data;        //返回栈顶的值
        S -> next = p -> next;      //栈顶位置变化
        free(p);        //释放栈顶空间
        return 1;
    }
}
//获取栈顶元素
int getTop(linkStack *S,int &ptr){      //不改变栈
    if(S -> next == NULL){
        printf("空\n");
        return 0;
    }
    ptr = S -> next -> data;
    return 1;
}

int main(){
    int x;      //读取出栈数据
    int y;
    linkStack *top;     //栈顶指针
    initStack(top);
    printf("对1，2进行入栈操作：\n");
    push(top,1);
    push(top,2);
    if(getTop(top,x) == 1){
        printf("获取栈顶元素：%d\n",x);
    }
    if(pop(top,y) == 1){
        printf("出栈元素：%d\n",y);
    }
    system("pause");
    return 0;
}